\chapter{Breaking the continuum hypothesis}
\label{ch:break_CH}
We now use the technique of forcing to break the
Continuum Hypothesis by choosing a good poset $\Po$.
As I mentioned earlier, one can also build a model
where the Continuum Hypothesis is true;
this is called the \emph{constructible universe} $L$.
However, I think it's more fun when things break\dots

%\section{Forcing $V \neq L$ is really easy}
%As a small aside, to check we're on the right track we show the following result.
%
%\begin{theorem}[$V \neq L$]
%	Let $M$ be a countable transitive model of $\ZFC$.
%	Let $\Po \in M$ be \emph{any} splitting poset,
%	and let $G \subseteq \Po$ be $M$-generic.
%	Then $M[G] \vDash (V \neq L)$.
%\end{theorem}
%\begin{proof}
%	Since $L$ has a $\Sigma_1$ definition,
%	we have \[ L^{M[G]} = L^M \subseteq M \subsetneq M[G] \]
%	where the last part follows from $G \notin M[G]$.
%\end{proof}
%
%Thus $M[G] \vDash \ZFC + (V \neq L)$ for any splitting poset $\Po$,
%and we are one step closer to breaking $\CH$.

\section{Adding in reals}
Starting with a \emph{countable} transitive model $M$.

We want to choose $\Po \in M$ such that $(\aleph_2)^M$ many real numbers appear,
and then worry about cardinal collapse later.

Recall the earlier situation where we set $\Po$ to be the infinite complete binary tree; its nodes can be thought of as partial functions $n \to 2$ where $n < \omega$.
Then $G$ itself is a path down this tree; i.e.\ it can be encoded as a total function $G \colon \omega \to 2$,
and corresponds to a real number.

\begin{center}
	\begin{asy}
		size(8cm);
		pair P = Drawing("\varnothing", (0,4), dir(90), red);
		pair P0 = Drawing("0", (-5,2), 1.5*dir(90), red);
		pair P1 = Drawing("1", (5,2),  1.5*dir(90));
		pair P00 = Drawing("00", (-7,0), 1.4*dir(120));
		pair P01 = Drawing("01", (-3,0), 1.4*dir(60), red);
		pair P10 = Drawing("10", (3,0),  1.4*dir(120));
		pair P11 = Drawing("11", (7,0),  1.4*dir(60));

		pair P000 = Drawing("000", (-8,-3));
		pair P001 = Drawing("001", (-6,-3));
		pair P010 = Drawing("010", (-4,-3), red);
		pair P011 = Drawing("011", (-2,-3));

		pair P100 = Drawing("100", (2,-3));
		pair P101 = Drawing("101", (4,-3));
		pair P110 = Drawing("110", (6,-3));
		pair P111 = Drawing("111", (8,-3));

		draw(P01--P0--P00);
		draw(P11--P1--P10);
		draw(P0--P--P1);
		draw(P000--P00--P001);
		draw(P100--P10--P101);
		draw(P010--P01--P011);
		draw(P110--P11--P111);

		draw(P--P0--P01--P010--(P010+2*dir(-90)), red+1.4);
		MP("G", P010+2*dir(-90), dir(-90), red);
	\end{asy}
\end{center}

We want to do something similar,
but with $\omega_2$ many real numbers instead of just one.
In light of this, consider in $M$ the poset
\[
	\Po = \opname{Add}(\omega, \omega_2)
	\defeq \left( \left\{ p \colon \omega_2 \times \omega \to 2,
		\dom(p) \text{ is finite} \right\},
	\supseteq \right).
\]
These elements $p$ (conditions) are ``partial functions'':
we take some finite subset of $\omega_2 \times \omega$ and map it into $2=\{0,1\}$.
(Here $\dom(p)$ denotes the domain of $p$,
which is the finite subset of $\omega_2 \times \omega$ mentioned.)
Moreover, we say $p \le q$ if $\dom(p) \supseteq \dom(q)$
and the two functions agree over $\dom(q)$.

\begin{ques}
	What is the maximum element $1_\Po$ here?
\end{ques}

\begin{exercise}
	Show that a generic $G$ can be encoded as a function $\omega_2 \times \omega \to 2$.
\end{exercise}

%Let $G \subseteq \opname{Add}(\omega, \omega_2)$ be an $M$-generic.
%We claim that, like in the binary case, $G$ can be encoded as a function $\omega_2 \times \omega \to 2$.
%To see this, consider $\alpha \in \omega_2$ and $n \in \omega$; we have the dense set
%\[ D_{\alpha, n}
%	= \left\{ p \in \opname{Add}(\omega, \omega_2)
%	\mid (\alpha, n) \in \dom(p) \right\}
%\]
%(this is obviously dense, given any $p$ add in $(\alpha, n)$ if it's not in there already).
%So $G$ hits this dense set, meaning that for every $(\alpha, n)$ there's a function in $G$ which defines it.
%Using the fact that $G$ is upwards closed and a filter, we may as before we may interpret $G$ as a function $\omega_2 \times \omega \to 2$.

\begin{lemma}[$G$ encodes distinct real numbers]
	For $\alpha \in \omega_2$ define
	\[ G_\alpha = \left\{ n \mid G\left( \alpha,n \right) = 0 \right\} \in \PP(\NN). \]
	Then $G_\alpha \neq G_\beta$ for any $\alpha \neq \beta$.
\end{lemma}
\begin{proof}
	We claim that the set
	\[ D = \left\{ q \mid \exists n \in \omega :
		q\left( \alpha, n \right) \neq q\left( \beta, n \right)
		\text{ are both defined}
	\right\} \]
	is dense.
	\begin{ques}
		Check this.
		(Use the fact that the domains are all finite.)
	\end{ques}
%	This is pretty easy to see.
%	Consider $p \in \opname{Add}(\omega, \omega_2)$.
%	Then you can find an $n$ such that
%	neither $(\alpha, n)$ nor $(\beta, n)$ is defined,
%	just because $\dom(p)$ is finite.
%	Then you make $p'$ as $p$ plus $p'( (\alpha, n) ) = 1$
%	and $p'( (\beta, n) ) = 0$.
%	Hence the set is dense.

	Since $G$ is an $M$-generic it hits this dense set $D$.
	Hence $G_\alpha \neq G_\beta$.
\end{proof}

Since $G \in M[G]$ and $M[G] \vDash \ZFC$,
it follows that each $G_\alpha$ is in $M[G]$.
So there are at least $\aleph_2^M$ real numbers in $M[G]$.
We are done once we can show there is no cardinal collapse.

\section{The countable chain condition}
It remains to show that with $\Po = \opname{Add}(\omega, \omega_2)$, we have that
\[ \aleph_2^{M[G]} = \aleph_2^M. \]
In that case, since $M[G]$ will have $\aleph_2^M = \aleph_2^{M[G]}$ many reals, we will be done.

To do this, we'll rely on a combinatorial property of $\Po$:
\begin{definition}
	We say that $A \subseteq \Po$ is a \vocab{strong antichain}
	if for any distinct $p$ and $q$ in $A$, we have $p \perp q$.
\end{definition}
\begin{example}[Example of an antichain]
	In the infinite binary tree,
	the set $A = \{00, 01, 10, 11\}$ is a strong antichain
	(in fact maximal by inclusion).
\end{example}
This is stronger than the notion of ``antichain'' than you might be used to!\footnote{%
	In the context of forcing, some authors use ``antichain'' to refer to ``strong antichain''.
	I think this is lame.}
We don't merely require that every two elements are incomparable,
but that they are in fact \emph{incompatible}.
\begin{ques}
	Draw a finite poset and an antichain of it which is not strong.
\end{ques}
\begin{ques}
	Convince yourself that all antichains in the infinite binary tree are strong, but some
	antichains in the poset $\Po$ defined above are not strong.
\end{ques}

\begin{definition}
	A poset $\Po$ has the \vocab{$\kappa$-chain condition}
	(where $\kappa$ is a cardinal) if all strong antichains
	in $\Po$ have size less than $\kappa$.
	The special case $\kappa = \aleph_1$ is called the \vocab{countable chain condition},
	because it implies that every strong antichain is countable.
\end{definition}

\begin{remark}[Notational digression: Why $<$ instead of $\leq$?]
	We could have defined that a poset $\Po$ has the $\kappa$-chain condition if all strong
	antichains in $\Po$ has size $\leq \kappa$. Nevertheless, this alternative definition is less
	versatile --- for instance, there would be no way to express that all strong antichains
	in $\Po$ are finite!
\end{remark}

We are going to show that if the poset has the $\kappa$-chain condition
then it preserves all cardinals $\geq \kappa$.
In particular, the countable chain condition will show that $\Po$ preserves all the cardinals.
Then, we'll show that $\opname{Add}(\omega, \omega_2)$ does indeed have this property.
This will complete the proof.

We isolate a useful lemma:
\begin{lemma}[Possible values argument]
	Suppose $M$ is a transitive model of $\ZFC$ and $\Po$ is a partial order
	such that $\Po$ has the $\kappa$-chain condition in $M$.
	Let $X,Y \in M$ and let $f \colon X \to Y$
	be some function in $M[G]$, but $f \notin M$.

	Then there exists a function $F \in M$, with $F \colon X \to \PP(Y)$ and such that
	for any $x \in X$,
	\[ f(x) \in F(x) \quad\text{and}\quad \left\lvert F(x) \right\rvert^M < \kappa. \]
\end{lemma}
What this is saying is that if $f$ is some new function that's generated,
$M$ is still able to pin down the values of $f$ to less than $\kappa$ many values.

\begin{proof}
	The idea behind the proof is easy: any possible value of $f$ gives us some condition in
	the poset $\Po$ which forces it.
	Since distinct values must have incompatible conditions,
	the $\kappa$-chain condition guarantees
	there are at most $\kappa$ such values.

	Here are the details.
	Let $\dot f$, $\check X$, $\check Y$ be names for $f$, $X$, $Y$.
	Start with a condition $p$ such that $p$ forces the sentence
	\[ \text{``$\dot f$ is a function from $\check X$ to $\check Y$''}. \]
	We'll work just below here.

	For each $x \in X$, we can consider (using the Axiom of Choice) a maximal strong antichain $A(x)$
	of incompatible conditions $q \le p$ which forces $f(x)$ to equal some value $y \in Y$.
	Then, we let $F(x)$ collect all the resulting $y$-values.
	These are all possible values, and there are less than $\kappa$ of them.
\end{proof}

\section{Preserving cardinals}
As we saw earlier, cardinal collapse can still occur.
For the Continuum Hypothesis we want to avoid this possibility,
so we can add in $\aleph_2^M$ many real numbers and have $\aleph_2^{M[G]} = \aleph_2^M$.
It turns out that to verify this, one can check a weaker result.

\begin{definition}
	For $M$ a transitive model of $\ZFC$ and $\Po \in M$ a poset,
	we say $\Po$ \vocab{preserves cardinals} if
	$\forall G \subseteq \Po$ an $M$-generic,
	the model $M$ and $M[G]$ agree on the sentence ``$\kappa$ is a cardinal'' for every $\kappa$.
	Similarly we say $\Po$ \vocab{preserves regular cardinals} if $M$ and $M[G]$
	agree on the sentence ``$\kappa$ is a regular cardinal'' for every $\kappa$.
\end{definition}
Intuition:
In a model $M$, it's possible that two cardinals which are in bijection in $V$ are no longer in bijection in $M$.
Similarly, it might be the case that some cardinal $\kappa \in M$ is regular,
but stops being regular in $V$ because some function $f \colon \ol\kappa \to \kappa$ is cofinal but happened to only exist in $V$.
In still other words, ``$\kappa$ is a regular cardinal'' turns out to be a $\Pi_1$ statement too.

Fortunately, each implies the other.
We quote the following without proof.
\begin{proposition}[Preserving cardinals $\iff$ preserving regular cardinals]
	Let $M$ be a transitive model of $\ZFC$.
	Let $\Po \in M$ be a poset.
	Then for any $\lambda$,
		$\Po$ preserves cardinalities less than or equal to $\lambda$
		if and only if $\Po$ preserves regular cardinals less than or equal to $\lambda$.
	Moreover the same holds if we replace ``less than or equal to''
	by ``greater than or equal to''.
\end{proposition}

Thus, to show that $\Po$ preserves cardinality and cofinalities
it suffices to show that $\Po$ preserves regularity.
The following theorem lets us do this:
\begin{theorem}[Chain conditions preserve regular cardinals]
	Let $M$ be a transitive model of ZFC, and let $\Po \in M$ be a poset.
	Suppose $M$ satisfies the sentence ``$\Po$ has the $\kappa$-chain condition and $\kappa$ is regular''.
	Then $\Po$ preserves regularity greater than or equal to $\kappa$.
\end{theorem}
\begin{proof}
	Use the Possible Values Argument.
	\Cref{prob:chain}.
\end{proof}

In particular, if $\Po$ has the countable chain condition then $\Po$ preserves \emph{all} the cardinals (and cofinalities).
Therefore, it remains to show that $\opname{Add}(\omega, \omega_2)$ satisfies the countable chain condition.

\section{Infinite combinatorics}
We now prove that $\opname{Add}(\omega, \omega_2)$ satisfies the countable chain condition.
This is purely combinatorial, and so we work briefly.

\begin{definition}
	Suppose $C$ is an uncountable collection of finite sets.
	$C$ is a \vocab{$\Delta$-system} if there exists a \vocab{root} $R$
	with the condition that for any distinct $X$ and $Y$
	in $C$, we have $X \cap Y = R$.
\end{definition}

\begin{lemma}
	[$\Delta$-System lemma] Suppose $C$ is an uncountable collection of finite sets.
	Then $\exists \ol C \subseteq C$ such that $\ol C$ is an uncountable $\Delta$-system.
\end{lemma}
\begin{proof}
	There exists an integer $n$ such that $C$ has uncountably many guys of length $n$.
	So we can throw away all the other sets, and just assume that all sets in $C$ have size $n$.

	We now proceed by induction on $n$.
	The base case $n=1$ is trivial, since we can just take $R = \varnothing$.
	For the inductive step we consider two cases.

	First, assume there exists an $a \in C$ contained in uncountably many $F \in C$.
	Throw away all the other guys.
	Then we can just delete $a$, and apply the inductive hypothesis.

	Now assume that for every $a$, only countably many members of $C$ have $a$ in them.
	We claim we can even get a $\ol C$ with $R = \varnothing$.
	First, pick $F_0 \in C$.
	It's straightforward to construct an $F_1$ such that $F_1 \cap F_0 = \varnothing$.
	And we can just construct $F_2, F_3, \dots$
\end{proof}

\begin{lemma}
	For all $\kappa$, $\opname{Add}(\omega, \kappa)$ satisfies the countable chain condition.
\end{lemma}
\begin{proof}
	Assume not. Let
	\[ \left\{ p_\alpha \mid \alpha < \omega_1 \right\} \]
	be a strong antichain.  Let
	\[ C = \left\{ \dom(p_\alpha) \mid \alpha < \omega_1 \right\}. \]
	Let $\ol C \subseteq C$ be such that $\ol C$ is uncountable, and $\ol C$ is a $\Delta$-system with root $R$.
	Then let
	\[ B = \left\{ p_\alpha \mid \dom(p_\alpha) \in R \right\}. \]
	Each $p_\alpha \in B$ is a function $p_\alpha \colon R \to \{0,1\}$,
	so there are two that are the same.
\end{proof}

Thus, we have proven that the Continuum Hypothesis cannot be proven in $\ZFC$.

\section\problemhead
\begin{problem}
	\label{prob:chain}
	Let $M$ be a transitive model of ZFC, and let $\Po \in M$ be a poset.
	Suppose $M$ satisfies the sentence ``$\Po$ has the $\kappa$-chain condition and $\kappa$ is regular''.
	Show that $\Po$ preserves regularity greater than or equal to $\kappa$.
	\begin{hint}
		Assume not, and take $\lambda > \kappa$ regular in $M$;
		if $f \colon \ol \lambda \to \lambda$,
		use the Possible Values Argument on $f$ to generate a function in $M$
		that breaks cofinality of $\lambda$.
	\end{hint}
	\begin{sol}
		It suffices to show that $\Po$ preserves regularity greater than or equal to $\kappa$.
		Consider $\lambda > \kappa$ which is regular in $M$,
		and suppose for contradiction that $\lambda$ is not regular in $M[G]$.
		That's the same as saying that there is a function $f \in M[G]$,
		$f \colon \ol \lambda \to \lambda$ cofinal, with $\ol \lambda < \lambda$.
		Then by the Possible Values Argument,
		there exists a function $F \in M$ from $\ol \lambda \to \PP(\lambda)$
		such that $f(\alpha) \in F(\alpha)$ and $\left\lvert F(\alpha) \right\rvert^M < \kappa$
		for every $\alpha$.

		Now we work in $M$ again.
		Note for each $\alpha \in \ol\lambda$,
		$F(\alpha)$ is bounded in $\lambda$ since $\lambda$ is regular in $M$ and
		greater than $\left\lvert F(\alpha) \right\rvert$.
		Now look at the function $\ol \lambda \to \lambda$ in $M$ by just
		\[ \alpha \mapsto \cup F(\alpha) < \lambda. \]
		This is cofinal in $M$, contradiction.
	\end{sol}
\end{problem}
